package testPackage;

public class Main {

    ListNode<Integer> deleteK(ListNode<Integer> head, int k) {
        if(head == null || k <= 0){
            return null;
        }
        ListNode<Integer> tempHead = head;
        int totalCount = 0;
        while (tempHead != null){
            tempHead = tempHead.next;
            totalCount ++;
        }
        if(k > totalCount){
            // 异常
            return null;
        }
        if(k == totalCount){
            // 删除首节点
            ListNode<Integer> res = head.next;
            head.next = null;
            return res;
        }
        // 删除中间节点
        // kPre,k的前一个节点
        ListNode<Integer> kPre = head;
        for(int i = 0; i < totalCount - k - 1; i++){
            kPre = kPre.next;
        }
        ListNode kNode = kPre.next;
        kPre.next = kPre.next.next;
        kNode.next = null;

        return head;
    }

    public static void main(String[] args) {
        ListNode<Integer> node1 = new ListNode<>(1);
        node1.next = new ListNode<>(2);
        node1.next.next = new ListNode<>(3);
        node1.next.next.next = new ListNode<>(4);
        node1.next.next.next.next = new ListNode<>(5);
        ListNode<Integer> deleteK = new Main().deleteK(node1, 5);
        while (deleteK != null){
            System.out.println(deleteK.value);
            deleteK = deleteK.next;
        }
    }

//
//    ListNode<Integer> solution2(ListNode<Integer> head, int k) {
//        if(head == null || k <= 0){
//            return null;
//        }
//        // 快
//        ListNode<Integer> node1 = head;
//        // 慢
//        ListNode<Integer> node2 = head;
//        for (int i = 0; i < k; i++) {
//            if(node1 == null){
//                return null;
//            }
//            node1 = node1.next;
//        }
//        while (node1 != null){
//            node1 = node1.next;
//            node2 = node2.next;
//        }
//        return node2;
//    }
//
    ListNode<Integer> findK(ListNode<Integer> head, int k) {
        if(head == null || k <= 0){
            return null;
        }
        ListNode<Integer> tempHead = head;
        int totalCount = 0;
        while (tempHead != null){
            tempHead = tempHead.next;
            totalCount ++;
        }
        if(k > totalCount){
            return null;
        }

        ListNode<Integer> res = head;
        for(int i = 0; i < totalCount - k; i++){
            res = res.next;
        }
        return res;
    }

}

class ListNode<T> {
    ListNode(T x) {
        value = x;
    }

    T value;
    ListNode<T> next;
}


